/*
 *      Filename: binTree.c
 *       Version: 0.1.0
 *   Description: 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组
 *                输入: 
 *                根据给定数组｛1, 2 ,3, 4,5, null, 6｝
 *                输出：
 *                返回一个由每层节点平均值组成的数组[1, 2.5, 5]
 *
 *        Author: wuyaowei
 *          Date: 2020-08-26
 *
 */
#include <stdlib.h>
#include <stdio.h>

typedef struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
} TreeNode;

#define MAX_LEN 10
//depth记录树的深度，sum保存每一层节点值的和，counter保存每层节点数
void avarageOfLevels(TreeNode *tree, int depth, int sum[], int counter[]) {
    if(tree == NULL) {
        return;
    }

    counter[depth]++;
    sum[depth] += tree->val;
    avarageOfLevels(tree->left, depth+1, sum, counter);
    avarageOfLevels(tree->right, depth+1, sum, counter);
}

//建树
TreeNode *createTree() {
    TreeNode *list = calloc(6, sizeof(TreeNode));
    
    for (int i = 0; i < 6; i++) {
      list[i].val = i+1;
    }

    list[0].left = list+1;
    list[0].right = list+2;
    list[1].left = list+3;
    list[1].right = list+4;
    list[2].left = NULL;
    list[2].right = list+5;
    return list;
}

void main() {
    int depth = 0;
    int sum[MAX_LEN] = {0};
    int counter[MAX_LEN] = {0};
    TreeNode *root = createTree();
    
    avarageOfLevels(root, depth, sum, counter);
    int i = 0;

    while(counter[i] !=0) {
	    printf("%.1f  ", sum[i]*1.0f / counter[i]*1.0f);
	    i++;
    }
    printf("\n");
}
